package src.leetcode.hot.mid_0117;

import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import src.tree.TreeNode;
public class connect {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5,null,7));
        TreeNode root = TreeNode.createTree(list);
        TreeNode.putTree(solution.connect(root));
    }
}


class Solution {
    public TreeNode connect(TreeNode root) {
        if (root == null) return root;
        Deque<TreeNode> que = new LinkedList<>();
        que.addFirst(root);
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.pollLast();
                if (i + 1 < size) {
                    node.next = que.peekLast();
                } else {
                    node.next = null;
                }

                if (node.left != null) {
                    que.addFirst(node.left);
                }
                if (node.right != null) {
                    que.addFirst(node.right);
                }
            }
        }
        return root;
    }
}